import java.util.Iterator;

public class Dijkstra {
	public static Map<String,ComparableAssociation<Integer,Edge<String,Integer>>> dijkstra(Graph<String,Integer> g, String start){
		// pre: g is a graph; start is source vertex
		// post: returns a dictionary of vertex-based results
		// value is association (total-distance,prior-edge)
		// keep a priority queue of distances from source
		PriorityQueue<ComparableAssociation<Integer,Edge<String,Integer>>> q = new SkewHeap<ComparableAssociation<Integer,Edge<String,Integer>>>();
		// results, sorted by vertex
		Map<String,ComparableAssociation<Integer,Edge<String,Integer>>> result = new Table<String,ComparableAssociation<Integer,Edge<String,Integer>>>();
		String v = start; // last vertex added
		// result is a (total-distance,previous-edge) pair
		ComparableAssociation<Integer,Edge<String,Integer>> possible = new ComparableAssociation<Integer,Edge<String,Integer>>(0,null);
		// as long as we add a new vertex...
		while (v != null){
			if (!result.containsKey(v)){
				// visit node v - record incoming edge
				result.put(v,possible);
				// vDist is shortest distance to v
				int vDist = possible.getKey();
				// compute and consider distance to each neighbor
				Iterator<String> ai = g.neighbors(v);
				while (ai.hasNext()){
					// get edge to neighbor
					Edge<String,Integer> e = g.getEdge(v,ai.next());
					// construct (distance,edge) pair for possible result
					possible = new ComparableAssociation<Integer,
					Edge<String,Integer>>(vDist+e.label(), e);
					q.add(possible); // add to priority queue
				}
			}
			// now, get closest (possibly unvisited) vertex
			if (!q.isEmpty()){
				possible = q.remove();
				// get destination vertex (take care w/undirected graphs)
				v = possible.getValue().there();
				if (result.containsKey(v))
					v = possible.getValue().here();
			} 
			else {
				// no new vertex (algorithm stops)
				v = null;
			}
		}
		return result;
	}
}
